One area in which computers are finding increased usage is in that of the graphical arts. Advances in speed, processing power, and memory capacity together with lower costs, have made computer graphics systems suited for simulating and displaying models of concrete or abstract objects. Moreover, computer generated models give users the capability to visualize and comprehend the structure of a single object and also the interaction and relationships between a group of objects. Furthermore, interactive computer graphics allows a user to input changes to a display. These changes are effectuated by the computer, which displays the resulting, modified images. For example, interactive computer graphics are being applied to video games, flight simulators, medical diagnostic displays, animated picture generators, computer-aided design, etc.
Basically, the display screens upon which computer-generated images are shown, are comprised of an array of picture elements. These picture elements are commonly referred to as "pixels". Each pixel represents a dot on the screen. Each of these pixels has associated parameter values which define certain attributes such as intensity, color (RGB), depth (Z), and blending (Alpha) for that particular pixel. The computer assigns parameter values for each pixel of the display screen for producing desired images. The parameter values are rendered into frame buffers, which are later read out for display. The aggregate of thousands of such pixels so programmed are used to represent physically displayed images on the display screen.
In order to simplify and increase the speed of the rendering and display process, complex or three-dimensional images are broken down into simple polygons, known as "primitives". It is easier and faster to rasterize whole polygons versus rasterization on a per pixel basis. Rasterization of primitives entails determining which pixels are to be updated for rendering that particular primitive. Additionally, rasterization involves the determination of how those pixels should be updated for creating a visually accurate display.
Primitives can take the shape of any of the polygons. For the sake of clarity, a triangular primitive is described herein. There exist many prior art techniques for determining which of the pixels of a triangular primitive should be modified for rendering that primitive. One such prior art technique involves "walking" along the edges of the triangle and generating horizontal or vertical spans of pixels from one edge to an opposing edge of the triangle.
Another prior art technique treats the triangle as the intersection of three half-planes. Each edge of the triangle is considered as an edge of one of the half-planes. Those pixels which fall "inside" each of the three half-planes are considered to be inside the triangle and are rendered. Pixels falling "outside" one or more of the half-planes are considered to be outside of the triangle and are not rendered.
The quality of the resulting images is improved if special attention is directed towards rasterizing those pixels near the borders of the triangle. Because the areas of these border pixels are partially inside and partially outside the boundaries of the triangle, their colors should be modified to reflect the proportion of the actual coverage. One prior art method involved computing an estimate of the pixel coverage. A new "blended" pixel value is generated in proportion to this estimated coverage.
One problem inherent to the coverage approach is that it is not possible to distinguish the effects of two triangles that abut in the vicinity of a pixel versus the effects of two triangles that obscure the same subregion of a pixel. For example, if triangle A covers 35% and triangle B covers 50% of a given pixel, it is not known whether triangle B covers the same 35% as triangle A plus 15%, if the 50% coverage of triage B is totally different from the 35% coverage of triangle A, or if the coverage falls somewhere in-between. Moreover, scalar coverages are difficult to merge correctly near the vertices of a single triangle, where the coverage values of two edges interact.
A better prior art technique for handling border pixels involves utilizing a mask. The mask is comprised of a number of bits corresponding to specific subregions of a pixel. The number of bits in a mask matches the actual area of half-plane coverage, often to a resolution of .+-. half a bit. For example, if the half-plane covers 52% of the pixel, and the mask is comprised of a total of 16 bits, then 8 or 9 of the bits are set while 7 or 8 bits are cleared. Those bits whose subregions most closely correspond to the pixel area that is covered by the half-plane are selected to be set. The bits are set and cleared independent of the orientation of the edge to the pixel.
However, problems arise due to the fact that typical mask generation techniques produce a mask that is based on an area of coverage, rather than precise evaluations at well defined points. Hence, area-based masks are often incompatible with existing z-buffering schemes (Z values stored in Z buffers correspond to the relative "depths" of display for eliminating "hidden" surfaces). In most cases, the Z values stored in the Z buffer can represent depth only for an exact point, rather than for an area of coverage. Applying area-based masks to graphics systems having multiple depth and color values for each pixel will sometimes compute inconsistent depth values for some of the subregions.
This problem is especially acute for those subregions whose center falls outside the actual geometry of the triangle. These inconsistent depth values might result in undesirable artifacts in the displayed images. An example of such an artifact is the protrusion of "bulkheads". A bulkhead is that part of a triangle that exactly abuts the interior of some other triangle. Hence, that part should not be visible since it is hidden behind the other triangle. Such bulkheads are improperly factored in the display if the mask generator is based on an area of coverage, whereas each subregion is treated as an exact location by the depth buffer computations.
Thus, there is a need in the computer graphics art for a rasterization process having a mask generator capable of point sampling. Point sampling treats each subregion of a pixel as a single sample point in order to achieve geometric accuracy. It would be preferable if such a mask generator could take advantage of rescaling, reduced-precision arithmetic, and table lookups for achieving an efficient implementation.